{"cells":[{"metadata":{},"cell_type":"markdown","source":"# **Devoir Maison – Première NSI**\n\n## Thématiques abordées\n- Recherche dichotomique (Binary Search)\n- Tri par insertion et rappel sur le tri\n- Tri par insertion *dichotomique*"},{"metadata":{},"cell_type":"markdown","source":"## Exercice 1 : Recherche dichotomique\nOn souhaite écrire une fonction `recherche_dichotomique(tab, valeur)` qui prend en paramètre :\n- `tab` : une liste de nombres triés par ordre croissant,\n- `valeur` : la valeur à chercher dans `tab`.\n\nLa fonction doit renvoyer l’**indice** où se trouve la valeur dans la liste si elle est présente, et `-1` sinon.\n\n### Rappels sur le principe de la recherche dichotomique\n1. On compare la valeur recherchée avec l’élément central de la liste.\n2. Si la valeur est égale à l’élément central, on a trouvé l’indice !\n3. Si la valeur est plus petite que l’élément central, on restreint la recherche à la sous-liste de gauche.\n4. Si la valeur est plus grande que l’élément central, on restreint la recherche à la sous-liste de droite.\n5. On répète le processus sur la sous-liste correspondante (elle-même coupée en deux, etc.).\n\n### À faire\n- Implémenter la fonction `recherche_dichotomique(tab, valeur)`.\n- Tester la fonction.\n"},{"metadata":{"trusted":true},"cell_type":"code","source":"def recherche_dichotomique(tab, valeur):\n    \"\"\"Recherche dichotomique d'une valeur dans un tableau trié.\n    Retourne l'indice de la valeur si trouvée, -1 sinon.\"\"\"\n    \n    # Compléter le code\n    debut = 0\n    fin = len(tab) - 1\n    \n    while debut <= fin:\n        # Calcul de l'indice central\n        milieu = (debut + fin) // 2\n        # Comparaison\n        if tab[milieu] == valeur:\n            return milieu  # Valeur trouvée\n        elif tab[milieu] < valeur:\n            debut = milieu + 1\n        else:\n            fin = milieu - 1\n    \n    return -1  # Valeur non trouvée\n\n# Tests\nliste_test = [1, 3, 5, 7, 9, 11]\nprint(recherche_dichotomique(liste_test, 7))   # Attendu : 3\nprint(recherche_dichotomique(liste_test, 2))   # Attendu : -1","execution_count":2,"outputs":[{"output_type":"stream","text":"3\n-1\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"## Exercice 2 : Rappel sur le tri\n### 2.1) Tri par sélection \nOn vous demande d'implémenter un algorithme de **tri par sélection** (*selection sort*).\n\n**Principe du tri par sélection :**\n1. On cherche l’élément minimum dans la liste complète, on l’échange avec l’élément à la position 0.\n2. Ensuite, on cherche le minimum dans la sous-liste qui commence à l’indice 1, et on l’échange avec l’élément en position 1.\n3. On recommence jusqu’à ce que la liste soit triée.\n\n**À faire :**\n- Implémenter la fonction `tri_selection(tab)`, qui trie en place la liste `tab`.\n- Tester la fonction."},{"metadata":{"trusted":true},"cell_type":"code","source":"def tri_selection(tab):\n    \"\"\"Trie la liste tab en place par sélection.\"\"\"\n    # Compléter le code\n    n = len(tab)\n    for i in range(n):\n        # Trouver l'index du minimum dans la sous-liste tab[i..n-1]\n        indice_min = i\n        for j in range(i+1, n):\n            if tab[j] < tab[indice_min]:\n                indice_min = j\n        # Échanger\n        tab[i], tab[indice_min] = tab[indice_min], tab[i]\n    return tab\n\n# Tests\nliste_test = [11, 3, 5, 7, 9, 1]\nprint(tri_selection(liste_test))  # Doit être triée : [1, 3, 5, 7, 9, 11]\n","execution_count":3,"outputs":[{"output_type":"stream","text":"[1, 3, 5, 7, 9, 11]\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"## **Exercice 3 : Tri par insertion dichotomique**\n\nDans cet exercice, nous allons mettre en œuvre un **tri par insertion** amélioré grâce à la **recherche dichotomique**.\n\nNous allons découper le travail en **deux parties** :\n- **Partie A** : Écrire la fonction qui détermine la position d’insertion par recherche dichotomique.\n- **Partie B** : Écrire le tri par insertion lui-même, qui utilisera la fonction de la Partie A.\n"},{"metadata":{},"cell_type":"markdown","source":"## Partie A\n### Position d’insertion par recherche dichotomique\n\nNous voulons une fonction `position_insertion_dichotomique(tab, debut, fin, valeur)` qui recherche la **position d’insertion** appropriée de `valeur` dans la sous-liste déjà triée `tab[debut..fin]`.\n\n#### Rappel de la recherche dichotomique\n1. On compare la `valeur` avec l’élément central de la sous-liste courante.\n2. Si `valeur` est plus petite, on réduit la recherche à la moitié gauche. Si elle est plus grande, on réduit à la moitié droite.\n3. On itère jusqu’à ce que `debut > fin`.\n4. Lorsque la boucle se termine, l’indice `debut` représente l’endroit où insérer la `valeur` (si elle n’est pas déjà présente).\n\n### Consignes\n1. Complétez la fonction ci-dessous pour qu’elle renvoie l’indice où insérer `valeur` **dans l’ordre croissant**.\n2. Faites quelques tests simples (vous pouvez utiliser une cellule en dessous) pour valider votre fonction."},{"metadata":{"trusted":true},"cell_type":"code","source":"def position_insertion_dichotomique(tab, debut, fin, valeur):\n    \"\"\"Retourne l'indice où insérer 'valeur' dans la sous-liste triée tab[debut..fin],\n    en utilisant une recherche dichotomique.\"\"\"\n    # TODO : À compléter\n    while debut <= fin:\n        milieu = (debut + fin) // 2\n        if tab[milieu] == valeur:\n            return milieu\n        elif tab[milieu] < valeur:\n            debut = milieu + 1\n        else:\n            fin = milieu - 1\n    return debut","execution_count":5,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Tests (Partie A)"},{"metadata":{"trusted":true},"cell_type":"code","source":"# Exemple de tests simples\nsous_liste = [1, 3, 5, 7, 9]\nprint(position_insertion_dichotomique(sous_liste, 0, 4, 4))  # Attendu 2\nprint(position_insertion_dichotomique(sous_liste, 0, 4, 10)) # Attendu 5 (en fin)\nprint(position_insertion_dichotomique(sous_liste, 0, 4, 0))  # Attendu 0 (en début)\nprint(position_insertion_dichotomique(sous_liste, 0, 4, 7))  # Attendu 3 (7 déjà présent)","execution_count":6,"outputs":[{"output_type":"stream","text":"2\n5\n0\n3\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"## Partie B\n### Tri par insertion dichotomique\n\nOn va maintenant utiliser notre fonction `position_insertion_dichotomique` pour créer un algorithme de **tri par insertion** :\n1. On considère que la partie `[tab(0)]` (le premier élément) est \"déjà triée\".\n2. On parcourt le tableau de l'indice `i = 1` jusqu’à `n-1`.\n3. Pour l’élément `tab[i]` :\n   - On trouve sa position d’insertion `pos` dans la sous-liste `tab[0..i-1]` (déjà triée) grâce à `position_insertion_dichotomique`.\n   - On décale les éléments pour laisser la place à la `valeur_a_inserer`.\n   - On insère `valeur_a_inserer` à l’indice `pos`.\n\n### Travail à faire\n- Compléter la fonction `insertion_dichotomique(tab)` ci-dessous.\n- Tester le résultat sur plusieurs listes différentes."},{"metadata":{"trusted":true},"cell_type":"code","source":"def insertion_dichotomique(tab):\n    \"\"\"Trie la liste 'tab' en place en utilisant\n    le tri par insertion et la recherche dichotomique.\"\"\"\n    # TODO : À compléter\n    n = len(tab)\n    for i in range(1, n):\n        valeur_a_inserer = tab[i]\n        # Trouver la position d'insertion dans la sous-liste triée tab[0..i-1]\n        pos = position_insertion_dichotomique(tab, 0, i-1, valeur_a_inserer)\n        \n        # Décaler les éléments vers la droite pour faire de la place\n        j = i\n        while j > pos:\n            tab[j] = tab[j - 1]\n            j -= 1\n        # Insérer la valeur dans la bonne position\n        tab[pos] = valeur_a_inserer\n    return tab","execution_count":7,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Tests (Partie B)\nEssayez plusieurs exemples et vérifiez si la liste est réellement triée à la fin."},{"metadata":{"trusted":true},"cell_type":"code","source":"liste_test1 = [5, 2, 9, 1, 3, 8]\nprint(\"Liste triée :\", insertion_dichotomique(liste_test1))  # [1, 2, 3, 5, 8, 9]\n\nliste_test2 = [10, 9, 8, 7, 2, 0]\nprint(\"Liste triée :\", insertion_dichotomique(liste_test2))  # [0, 2, 7, 8, 9, 10]\n\nliste_test3 = [1]\nprint(\"Liste triée :\", insertion_dichotomique(liste_test3))  # [1]\n\nliste_test4 = []\nprint(\"Liste triée :\", insertion_dichotomique(liste_test4))  # []","execution_count":8,"outputs":[{"output_type":"stream","text":"Liste triée : [1, 2, 3, 5, 8, 9]\nListe triée : [0, 2, 7, 8, 9, 10]\nListe triée : [1]\nListe triée : []\n","name":"stdout"}]},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}},"nbformat":4,"nbformat_minor":2}